1. Field of the Invention
The present invention generally relates to data hiding and authentication techniques and, more particularly, to a method and apparatus for embedding and extracting auxiliary images imperceptibly into a source image by modified halftoning algorithms.
2. Description of the Related Art
Recently, there has been much interest in data hiding, where information is imperceptibly embedded into multimedia content such as images. The embedded data can be ownership identification, tracking information, recipient information, time stamps, authentication data, and other information useful for various applications such as copyright protection, data integrity verification, verification of origin of data, recipient tracking, etc.
However, prior to the present invention, there have been few efficient methods in which entire images can be embedded into a source image. Indeed, many previous data hiding schemes can only embed a small amount of information into a source image.
Further, there have been few methods in which the embedded image can be used to identify, localize and reverse tampering to images. Previous methods to reverse tampering can only recover a heavily degraded version of the original image.
In one conventional approach, as described, for example, in K. Knox, “Reversible Digital Images”, IS&T/SPIE Conference on Security and Watermarking of Multimedia Contents, 1999, pp. 397–401, a system was proposed to embed an image into another image.
However, in this conventional approach, two separate error diffusion algorithms are applied independently to the two images, and therefore the choice of the output colors is not as ideal as the present invention described below.
Secondly, the extraction algorithm in Knox's approach is based on reversing the bits of the pixels. This corresponds to a set C in the present invention of the form (a,r(a)) where r(a) is a with the bits reversed. This function r is very discontinuous yet there is a portion of [0,255]2 which the convex hull of C does not cover. Thus, in the conventional approach, the set C cannot be chosen to be any set of the form (a,f(a)) and the function f cannot be chosen depending on the application. That is, in the conventional approach, f cannot be selected to be smooth for more robustness, nor can f be chosen so that the convex hull of C covers a large portion of [0,255]2. Indeed, in the conventional approach, the function r is one-to-one, while in the present invention, the function f does not have to be one-to-one.